/*************************************************************************
	> File Name: 239.滑动窗口最大值.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 二  9/ 7 18:44:53 2021
 ************************************************************************/

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){
    int que[numsSize]; //保存数组下标，下标对应的数组中的值是单调递减的
    int head = 0, tail = 0;
    for (int i = 0; i < k; i++) {
        while (head < tail && nums[i] >= nums[que[tail - 1]]) {
            tail--;
        }
        que[tail++] = i;
    }
    *returnSize = 0;
    int *ret = malloc(sizeof(int) * (numsSize - k + 1));
    ret[(*returnSize)++] = nums[que[head]];
    for (int i = k; i < numsSize; i++) {
        while (head < tail && nums[i] >= nums[que[tail - 1]]) {
            tail--;
        }
        que[tail++] = i;
        while (que[head] <= i - k) { //判断单调队列的队首元素是否在滑动窗口中
            head++;
        }
        ret[(*returnSize)++] = nums[que[head]];
    }
    return ret;
}
